home *** CD-ROM | disk | FTP | other *** search
/ Whiteline: Alpha / Whiteline Alpha.iso / progtool / c / mint110 / nalloc2.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-22  |  6.3 KB  |  269 lines
  1. /*
  2.  * Copyright 1992,1993 Atari Corporation.
  3.  * All rights reserved.
  4.  */
  5.  
  6. /*
  7.  * General-purpose memory allocator, on the MWC arena model, with
  8.  * this added feature:
  9.  *
  10.  * All blocks are coalesced when they're freed.  If this results in
  11.  * an arena with only one block, and that free, it's returned to the
  12.  * OS.
  13.  *
  14.  * The functions here have the same names and bindings as the MWC
  15.  * memory manager, which is the same as the UNIX names and bindings.
  16.  *
  17.  * MiNT version: used for kmalloc to manage kernel memory in small hunks,
  18.  * rather than using a page at a time.
  19.  */
  20.  
  21. #include "mint.h"
  22.  
  23. #if 0
  24. #define NALLOC_DEBUG(c) TRACE(("nalloc: %c",c));
  25. #else
  26. #define NALLOC_DEBUG(c) /* nothing */
  27. #endif
  28.  
  29. #define NKMAGIC 0x19870425L
  30.  
  31. /*
  32.  * block header: every memory block has one.
  33.  * A block is either allocated or on the free
  34.  * list of the arena.  There is no allocated list: it's not necessary.
  35.  * The next pointer is only valid for free blocks: for allocated blocks
  36.  * maybe it should hold a verification value..?
  37.  *
  38.  * Zero-length blocks are possible and free; they hold space which might 
  39.  * get coalesced usefully later on.
  40.  */
  41.  
  42. struct block {
  43.     struct block *b_next;   /* NULL for last guy; next alloc or next free */
  44.     long b_size;
  45. };
  46.  
  47. /*
  48.  * arena header: every arena has one.  Each arena is always completely
  49.  * filled with blocks; the first starts right after this header.
  50.  */
  51.  
  52. struct arena {
  53.     struct arena *a_next;
  54.     struct block *a_ffirst;
  55.     long a_size;
  56. };
  57.  
  58. /*
  59.  * Arena linked-list pointer, and block size.
  60.  */
  61.  
  62. static struct arena *a_first = (struct arena *)NULL;
  63.  
  64. void
  65. nalloc_arena_add(start,len)
  66. void *start;
  67. long len;
  68. {
  69.     struct arena *a;
  70.     struct block *b;
  71.  
  72.     for (a = a_first; a && a->a_next; a = a->a_next)
  73.     continue;
  74.     if (a)
  75.         a->a_next = (struct arena *)start;
  76.     else
  77.         a_first = (struct arena *)start;
  78.     a = start;
  79.     a->a_next = NULL;
  80.     a->a_ffirst = b = (struct block *)(a+1);
  81.     a->a_size = len - sizeof(*a);
  82.     b->b_next = NULL;
  83.     b->b_size = (len - sizeof(*a) - sizeof(*b));
  84. }
  85.     
  86.  
  87. void *
  88. nalloc(size)
  89. long size;
  90. {
  91.     struct arena *a;
  92.     struct block *b, *mb, **q;
  93.     long temp;
  94.  
  95.     NALLOC_DEBUG('A');
  96.  
  97.     /* force even-sized alloc's */
  98.     size = (size+1) & ~1;
  99.  
  100.     for (a = a_first; a; a = a->a_next) {
  101.     for (b = *(q = &a->a_ffirst); b; b = *(q = &b->b_next)) {
  102.         /* if big enough, use it */
  103.         if (b->b_size >= (size + sizeof(struct block))) {
  104.  
  105.         /* got one */
  106.         mb = b;
  107.  
  108.         /* cut the free block into an allocated part & a free part */
  109.         temp = mb->b_size - size - sizeof(struct block);
  110.         if (temp >= 0) {
  111.             /* large enough to cut */
  112.             NALLOC_DEBUG('c');
  113.             b = (struct block *)(((char *)(b+1)) + size);
  114.             b->b_size = temp;
  115.             b->b_next = mb->b_next;
  116.             *q = b;
  117.             mb->b_size = size;
  118.             mb->b_next = (struct block *)NKMAGIC;
  119.         }
  120.         else {
  121.             /* not big enough to cut: unlink this from free list */
  122.             NALLOC_DEBUG('w');
  123.             *q = mb->b_next;
  124.         }
  125.         return (void *)(mb+1);
  126.         }
  127.     }
  128.     }
  129.  
  130.     /* no block available: get a new arena */
  131.  
  132. #if 1
  133.     return NULL;    /* MiNT: fail. */
  134. #else
  135.     if (!minarena) {
  136.     minarena = Malloc(-1L) / 20;
  137.     if (minarena > MAXARENA) minarena = MAXARENA;
  138.     }
  139.  
  140.     if (size < minarena) {
  141.     NALLOC_DEBUG('m');
  142.     temp = minarena;
  143.     }
  144.     else {
  145.     NALLOC_DEBUG('s');
  146.     temp = size;
  147.     }
  148.  
  149.     a = (struct arena *)Malloc(temp + 
  150.                 sizeof(struct arena) +
  151.                 sizeof(struct block));
  152.  
  153.     /* if Malloc failed return failure */
  154.     if (a == 0) {
  155.         NALLOC_DEBUG('x');
  156.         return 0;
  157.     }
  158.  
  159.     a->a_size = temp + sizeof(struct block);
  160.     a->a_next = a_first;
  161.     a_first = a;
  162.     mb = (struct block *)(a+1);
  163.     mb->b_next = NULL;
  164.     mb->b_size = size;
  165.  
  166.     if (temp > (size + sizeof(struct block))) {
  167.         NALLOC_DEBUG('c');
  168.     b = a->a_ffirst = ((char *)(mb+1)) + size;
  169.     b->b_next = NULL;
  170.     b->b_size = temp - size - sizeof(struct block);
  171.     }
  172.     else {
  173.     a->a_ffirst = NULL;
  174.     }
  175.     return (void *)(++mb);
  176. #endif
  177. }
  178.  
  179. void
  180. nfree(start)
  181. void *start;
  182. {
  183.     struct arena *a, **qa;
  184.     struct block *b;
  185.     struct block *pb;
  186.     struct block *fb = (struct block *)start;
  187.  
  188.     NALLOC_DEBUG('F');
  189.     if (fb->b_next != (struct block *)NKMAGIC) {
  190.     FATAL("nfree: block %lx not allocated by nalloc!",fb);
  191.     }
  192.  
  193.     /* set fb (and b) to header start */
  194.     b = --fb;
  195.  
  196.     /* the arena this block lives in */
  197.     for (a = *(qa = &a_first); a; a = *(qa = &a->a_next)) {
  198.     if ((unsigned long)b > (unsigned long)a &&
  199.         (unsigned long)b < (((unsigned long)a) + a->a_size)) goto found;
  200.     }
  201.     FATAL("nfree: block %lx not in any arena!",fb);
  202.  
  203. found:
  204.     /* Found it! */
  205.     /* a is this block's arena */
  206.  
  207.     /* set pb to the previous free block in this arena, b to next */
  208.     for (pb = NULL, b = a->a_ffirst;
  209.      b && (b < fb);
  210.      pb = b, b = b->b_next) ;
  211.  
  212.     fb->b_next = b;
  213.  
  214.     /* Coalesce backwards: if any prev ... */
  215.     if (pb) {
  216.     /* if it's adjacent ... */
  217.     if ((((unsigned long)(pb+1)) + pb->b_size) == (unsigned long)fb) {
  218.         NALLOC_DEBUG('b');
  219.         pb->b_size += sizeof(struct block) + fb->b_size;
  220.         fb = pb;
  221.     }
  222.     else {
  223.         /* ... else not adjacent, but there is a prev free block */
  224.         /* so set its next ptr to fb */
  225.         pb->b_next = fb;
  226.     }
  227.     }
  228.     else {
  229.     /* ... else no prev free block: set arena's free list ptr to fb */
  230.     a->a_ffirst = fb;
  231.     }
  232.  
  233.     /* Coalesce forwards: b holds start of free block AFTER fb, if any */
  234.     if (b && (((unsigned long)(fb+1)) + fb->b_size) == (unsigned long)b) {
  235.     NALLOC_DEBUG('f');
  236.     fb->b_size += sizeof(struct block) + b->b_size;
  237.     fb->b_next = b->b_next;
  238.     }
  239.  
  240.     /* if, after coalescing, this arena is entirely free, Mfree it! */
  241.     if ((struct arena *)a->a_ffirst == a+1 && 
  242.         (a->a_ffirst->b_size + sizeof(struct block))== a->a_size &&
  243.         a != a_first) {
  244.         NALLOC_DEBUG('!');
  245.         *qa = a->a_next;
  246. #if 1
  247.         kfree(a);    /* MiNT -- give back so it can be used by users */
  248. #else
  249.         (void)Mfree(a);
  250. #endif
  251.     }
  252.  
  253.     return;
  254. }
  255.  
  256. void
  257. NALLOC_DUMP()
  258. {
  259.     struct arena *a;
  260.     struct block *b;
  261.  
  262.     for (a = a_first; a; a = a->a_next) {
  263.     FORCE("Arena at %lx size %lx: free list:",a,a->a_size);
  264.     for (b = a->a_ffirst; b; b = b->b_next) {
  265.         FORCE("    %8lx size %8lx",b,b->b_size);
  266.     }
  267.     }
  268. }
  269.